// 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。

// 暴露接口
const splitArray = function (nums: number[], m: number): number {
    const maxElem = Math.max(...nums); // 求最大元素
    const sum: number = nums.reduce((a, b) => a + b); // 求总和
    let left = maxElem;// 左指针
    let right = sum;// 右指针
    // 二分查找算法
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const subArrCount = splitArrayCalCount(nums, mid);
        // 子数组计数小了，说明子数组和限制大了
        if (subArrCount < m) {
            right = mid - 1;
            // 子数组计数大了，说明子数组和限制小了
        } else if (subArrCount > m) {
            left = mid + 1;
            // 与分割数组个数对应时，因为求最小所以需要最大和限制更小
        } else if (subArrCount === m) {
            right = mid;
        }
    }
    return left;
};

// 根据限制的最大的子数组和计算可以分割的连续子数组
function splitArrayCalCount(nums: number[], maxSubArrSum: number): number {
    let subArrCount = 1;// 子数组个数，最小为1
    let currSum = 0;// 当前累加和
    for (let num of nums) {
        // 如果未超过最大子数组和限制则直接加入，这里的等号重要
        if (currSum + num <= maxSubArrSum) {
            currSum += num;
        } else {
            // 重置状态并添加子数组计数
            currSum = num;
            subArrCount++;
        }
    }
    return subArrCount;
}

splitArray([7, 2, 5, 10, 8], 2)


// 这道题目是一道细节处理较为琐碎，难度较大的题目
// 主要考察的二分搜索算法应用其实并不太好直接想到。
// 首先，这个题目非常关键的字眼是：非负整数数组、非空 和 连续。
// 尤其是「非负整数数组」和「连续」这两个信息。使用二分查找具有要求数组范围区间连续的要求
// 而针对于这道题目，存在隐藏的数据单调性：
// 即如果限定「连续数组各自和的最大值」很大，那么必然导致分割数很小；
// 否则限定「连续数组各自和的最大值」很小，那么必然导致分割数很大；
// 仔细想想，这里「数组各自和的最大值」就决定了一种分割的方法。
// 再联系一下我们刚刚向大家强调的题目的要求 连续 和题目中给出的输入数组的特点: 非负整数数组。
// 那么，我们就可以通过调整「数组各自和的最大值」来达到：使得分割数恰好为 m 的效果。
// 而在求解过程中 "最大的子数组和" 存在明确的取值范围：[最大的元素, 元素之和]
// 它们分别对应的子数组长度为：数组长度和1
// 现在把问题反过来求，不求分割成m个子数组对应的最大子数组和，
// 我们来求当最大连续子数组和等于x时数组被分割成了多少个子数组，x的范围就是[最大的元素, 元素之和]
// 上述的过程可以通过不断地遍历整个数组来求解出长度
// 而数据范围又存在单调有序性，故可以通过二分搜索算法求解。